The invention relates to self-tuning buffer management.
Computer systems have limited memory storage for the information they process, and in some cases, the amount of information to be processed may exceed the amount of available storage. Buffering systems, such as caches, allow only a subset of the information to be stored in memory at any given time. Information stored in the buffers typically can be retrieved more quickly than information stored, for example, on a magnetic or optical disk.
A buffer manager is responsible for managing the buffers. For example, to store new data in the cache when the cache is full, at least some data already residing in the cache must be replaced. Various replacement strategies are known including replacing the least recently used (LRU) data. In general, such strategies also involve rearranging the relative positions of the buffers within the pool. For example, one implementation of the LUR technique maintains the list of buffers according to the time at which the data in each buffer is accessed. At one end (the xe2x80x9chotxe2x80x9d end) of the list is a buffer containing the most recently used data, and at the other end (the xe2x80x9ccoldxe2x80x9d end) is a buffer containing the least recently used data. When data in a given buffer is accessed, the buffer containing the data is moved from its current location in the list to the hot end of the list. When new data is brought into the cache, it is placed in the buffer at the cold end of the list, and the buffer then is moved to the hot end of the list.
A considerable amount of overhead is required to rearrange the buffers each time data is accessed. This rearranging also can lead to contention for buffer data structures, limiting the amount of parallelism that can be achieved in the buffer manager. Reducing contention is an important way to enable a multi-CPU (central processing unit) system to run faster, so that the CPUs do not have to wait for each other as much. Therefore, it would desirable to improve management of the buffers.
In general, a method of managing memory buffers includes maintaining a pool of buffers and assigning the buffers to buffer classes based on the frequency with which information stored in the buffers is accessed. Different algorithms can be used to manage buffers assigned to the different classes.
Various implementations can include one or more of the following features. A determination can be made as to whether a particular buffer qualifies for entry into a particular one of the buffer classes based on a comparison between a threshold value and the frequency with which information stored in the particular buffer was accessed during a specified time interval.
The threshold value can be adjusted dynamically. For example, if it is determined that too many buffers have qualified for entry into the particular buffer class, the threshold value can be increased. If it is determined that too few buffers have qualified for entry into the particular buffer class, the threshold value can be decreased. The particular buffer class can have a target size, and the threshold value can be adjusted based on the number of attempts to assign buffers to the particular buffer class that would cause the target size to be exceeded. In some cases, the target size represents a maximum permissible size for the particular buffer class. In general, the technique can include periodically checking the extent of any disparity between a target size for the particular buffer class and the number of buffers that qualified for the particular buffer class during a previous time interval and adjusting the threshold value based on the extent of the disparity.
In some situations, a user can designate particular information as a candidate for storage in a particular buffer class. The techniques then can include determining whether requested information was previously designated by a user as a candidate for storage in a particular buffer class and comparing the frequency with which the requested information was accessed during a specified time interval to a threshold value. If the requested information was previously designated by a user as a candidate for storage in the particular buffer class and the frequency with which the information was accessed during the specified time interval is greater than the threshold value, then the requested information is stored in a buffer in the particular buffer class.
A system that includes first and second memories, a bus and a processor configured to execute the foregoing techniques also is disclosed. Furthermore, an article that includes a computer-readable medium that stores computer-executable instructions for causing a computer system to execute the foregoing techniques is disclosed.
Some implementations include one or more of the following advantages. The techniques can allow buffers to be assigned to a buffer class based on how frequently the buffers are accessed. The techniques can help ensure that buffers that previously were accessed frequently but are no longer being accessed frequently are moved to lower priority classes. Thus, buffers can be prevented from becoming permanently labeled as containing frequently-accessed data when the data no longer is being accessed frequently.
Adjustments to the thresholds can be made dynamically to take account, for example, of the current load on the system. The adjustments can be implemented automatically by the system without user intervention and can increase the overall efficiency and cost-effectiveness of the system.
Other features and advantages will be readily apparent from the following detailed description, the accompanying drawings and the claims.